1. 题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：输入： 2 输出： 2 解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶

示例 2：输入： 3 输出： 3 解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/climbing-stairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

2.1. 动态规划

动态规划入门题了。dp[n] = dp[n-1]+dp[n-2]。dp[0]=1，dp[1]=1。

然后发现，这不是斐波那契数列吗？？

说起斐波那契数列，那解法就多起来了。

2.2. 比内公式

设斐波那契数列为f[i]，f[0]=0，f[1]=1，f[2]=1，f[3]=2，f[4]=3...

则dp[i]=f[i+1]

比内公式： $f[n]=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$

2.3. 矩阵快速幂

亦可如下推导：

3. 代码

3.1. 动态规划

下述代码可进行空间优化

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1,1);
        for(int i=2;i<=n;++i){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

3.2. 比内公式

class Solution {
public:
    int climbStairs(int n) {  
        double a=(1+sqrt(5))/2;
        double b=(1-sqrt(5))/2;
        //精度不够，数据过大可能会有偏差
        return (pow(a,n+1)-pow(b,n+1))/sqrt(5);//dp[i]=f[i+1]
    }
};

3.3. 矩阵快速幂

class Solution {
    public int[][] times(int[][] a, int[][] b){
        int[][] c = new int[2][2];
        for(int i=0;i<2;++i){
            for(int j=0;j<2;++j){
                c[i][j]=0;
                for(int k=0;k<2;++k){
                    c[i][j]+=a[i][k]*b[k][j];
                }
            }
        }
        return c;
    }

    public int[][] quickPower(int[][] x, int y){
        int[][] res = {{1,0},{0,1}};
        while(y>0){
            if((y&1)>0) res = times(res,x);
            x = times(x,x);
            y>>=1;
        }
        return res;
    }

    public int climbStairs(int n) {
        int[][] q = {{1,1},{1,0}};
        int[][] ans = quickPower(q,n);
        return ans[0][0];
    }
}

70 爬楼梯